The proliferation of smart phones and other mobile devices has placed more processing power in the hands of consumers than ever before. These mobile devices are capable of executing a variety of applications, including applications that assist with navigation and route-finding. Traditional global positioning system (GPS) navigation devices are used to assist automobile owners with driving operations from a source to a destination, and navigation software is generally developed with the use-case of driving directions in mind. These devices may provide map data in the form of a road graph, with valid driving paths represented by line segments which intersect at various points, and which have a directionality element indicating valid directions of travel along the line segments. Such a design is efficient for use in situations where the user is travelling via a vehicle, as the vehicle is limited to particular pathways of travel.
However, as mobile devices increasingly contain route finding software, various solutions that provide for walking and indoor navigation have also been developed. In particular, walking and indoor navigation environments do not typically conform to easy representation via a series of interconnected line segments. These environments may include non-uniformly shaped open spaces that intersect across line segments, instead of at points. Generation of map representations of these environments using traditional road graph models may not accurately capture the relationship between possible destinations and navigable paths.